1. Field of the Invention
The present invention relates to data packet scheduling. The present invention provides a method, system and computer program that not only provides proportional fairness in scheduling, but also provides a constant normalized worst-case fair index to maintain short term and long-term fairness when scheduling data packets.
2. Description of the Related Art
When conducting data communications over a network, for example, the Internet, a router is utilized to route data to a given destination on the Internet. A router is a device, or in some cases, software in a computer, that determines the next destination on the network for a data packet (a unit of data that is routed between an origin and a destination on the Internet or any other packet-switched network). The router may be connected to at least two networks and may decide which way to send each data packet based on its current understanding of the state of the networks. Because data communications occur using a finite bandwidth, a router must schedule the output of data packets from the router to the connected networks.
A packet scheduler determines the order of data packets to be served (transmitted) by the router, and thus, the bandwidth allocation for each flow (data transmitted on one or more data lines, such as between computers or devices or between nodes in a network). Packet scheduling has been extensively studied in the last decade due to its importance in providing quality of service (QoS) guarantees in data networks. QoS entails ensuring that a data packet is scheduled to be output by the router within a certain time period after it is received. When scheduling a data packet, an ideal packet scheduler should have the following three properties. First, the packet scheduler should have a low complexity, preferably having a complexity of order 1 (O(1)). Having a complexity of O(1) allows the packet scheduler to be used in high-speed networks because the complexity does not depend on the number of flows in the system. Second, the packet scheduler should incur a bounded delay for each packet which reaches the head of a scheduling queue for a flow in order for the packet scheduler to provide QoS. Lastly, the packet scheduler should provide fairness among the flows (data transmitted on one or more data lines) competing for a shared link of the router to ensure that each flow receives a fair share of the bandwidth for outputting data packets.
Two fairness criteria for scheduling data packets are worst-case fairness and proportional fairness. Worst-case fairness requires the flow rates of all flows in the system to be maintained within a small error margin. Therefore, a packet scheduler, s, may provide a worst-case fairness for a flow fi, if the delay of a data packet arriving at time t on flow fi is bounded by the equation
                              Q                      i            ,            s                          ⁡                  (          t          )                            r        i              +          C              i        ,        s              ,where Qis(t) is the queue size of fi at time t, ri is the assured rate of fi, and Ci,s is a constant independent of the queues of other flows.
A packet scheduler is worst-case fair if it is worst-case fair to all flows in the system. If a packet scheduler, s, is worst-case fair, the fairness of the packet scheduler is measured by a normalized worst-case fair index. The normalized worst-case fair index for the scheduler, cs, is defined as
      c    s    =            max      i        ⁢          {                                    r            i                    ⁢                      C                          i              ,              s                                      R            }      where R is the total link bandwidth for the router.
Proportional fairness requires that data bandwidths be allocated by the router to any two backlogged flows which are proportional to their weights (assured rates) at all times within a small error margin. To achieve both long term and short-term fairness, a packet scheduler should provide both worst-case fairness and proportional fairness. Existing scheduling algorithms can be classified into two types, a timestamp based algorithm and a round robin algorithm. Timestamp based algorithms have good bounded delay and fairness properties, but have a relatively high complexity, O(log N), where N is the number of flows in the system. Thus, the implementation of timestamp-based algorithms in high-speed networks is problematic due to the logarithmic complexity of the timestamp-based algorithm. Round robin algorithms have a relatively low, or order 1 complexity, but in general do not have good bounded delay and fairness properties. For example, existing round robin schemes fail to achieve a constant normalized worst-case fair index.
Round robin schedulers serve backlogged flows for data packets in a round robin fashion and have an O(1) per packet processing complexity. To achieve fairness with different packet sizes, a Deficit Round Robin (DRR) scheme augments the traditional round robin algorithm. The DRR uses a deficit counter and a quantum, or expected amount of data to be sent in one round, for each flow in addition to the standard round robin algorithm.
A number of methods have recently been proposed to improve delay and burstiness (a specific amount of data sent or received in one intermittent operation) properties of the DRR algorithm. A Smoothed Round Robin (SRR) approach improves the delay and burstiness properties by spreading the data of a flow to be transmitted in a round of data transmission over the entire round using a weight spread sequence to order packets. An Aliquem approach allows the quantum of a flow to be scaled down by making the quantum smaller that a maximum packet size, which results in better delay and burstiness properties. Both the SRR approach and the Aliquem approach improve the average data packet delay over the DRR algorithm. However, the worst-case single packet delay is proportional to the number of flows in the system. Like the SRR approach, a Stratified Round Robin approach also tries to spread the data of a flow by using a deadline based scheduling scheme to ensure that all flows receive fair access to the router from the packet scheduler. The Stratified Round Robin has a single packet delay which is related to a definite rate of the flow and is independent of the number of flows in the system.
A Bin Sort Fair Queuing (BSFQ) approach uses an approximate bin sort mechanism to schedule packets. When implementing the BFSQ approach, the worst-case single packet delay is proportional to the number of flows in the system. Hybrid round robin scheduling approaches have also been proposed. In a hybrid approach, the scheduling tasks are separated into two levels. Despite the myriad of round robin schemes, none of existing round robin approaches has a constant normalized worst-case fair index.
Accordingly, there is a need and desire for a packet scheduler that provides an O(1) complexity while maintaining proportional fairness and a normalized worst-case fair index.